/***************************************************************************
													mstl.h	-  Mini-STL library
														 -------------------
		begin 							 : Mon May 6 2002
		copyright 					 : (C) 2002 by Michiel Visser
		email 							 :
 ***************************************************************************/

/***************************************************************************
 *																																				 *
 *	 This program is free software; you can redistribute it and/or modify  *
 *	 it under the terms of the GNU General Public License as published by  *
 *	 the Free Software Foundation; either version 2 of the License, or		 *
 *	 (at your option) any later version.																	 *
 *																																				 *
 ***************************************************************************/

//---------------------------------------------------------------------------
#ifndef __MSTL_ALLOC_H__
#define __MSTL_ALLOC_H__
//---------------------------------------------------------------------------

#include "mstl_dbg.h"
#include <typeinfo>
#include <malloc.h>
#include <new>

#ifndef __WIN__
void *_aligned_malloc(size_t size, size_t alignment);
void _aligned_free(void *ptr);
#endif

#if !defined(MALLOC_FREE_TEST) && !defined(MALLOC_COUNT) && !defined(MALLOC_BOUNDARY_TEST)
#ifdef MALLOC_SIMPLE_TRACE
#define mstl_alloc(s) _mstl_alloc(s,__FILE__,__LINE__)
inline void *_mstl_alloc( size_t s, const char *f, int l) throw (bad_alloc) { return malloc(s); }
#else
#define mstl_alloc malloc
#endif
inline void mstl_free( void *p) { free(p); }
#else
void *mstl_alloc( size_t s);
void mstl_free( void *p);
#endif

inline void * operator new	 ( size_t s) throw (std::bad_alloc) { return mstl_alloc(s); }
inline void * operator new[] ( size_t s) throw (std::bad_alloc) { return mstl_alloc(s); }

inline void operator delete(void *p) { mstl_free(p); }

inline void operator delete[](void *p) { mstl_free(p); }

inline void *reserveBytes(int num ) { return mstl_alloc(num); }
template<typename T> inline void *reserveBytes(int num ) { return mstl_alloc(num);}

template<typename T> inline void freeBytes(void *v ) { mstl_free(v); }
template<typename T> inline void freeObject(T *p) { p->~T();freeBytes<T>(p); }


template<typename T> struct Create
{ static T * fromSpace(void *space) { return new (space) T(); }
	template<typename S> static T *fromSpace(void *space, const S &param) { return new (space) T(param); }
	template<typename S> static T *aNew(const S &param) { return new (reserveBytes<T>(sizeof(T))) T(param); }
	static T *aNew() { return new (reserveBytes<T>(sizeof(T))) T(); }
	static T *aNewArray(int count) { return new T[count]; }
};

inline void bitSet(unsigned int *v, int bit) { v[bit>>5]|=1<<(bit&0x1f); }
inline void bitSet(unsigned int *v, int bit, int value) { v[bit>>5]=(v[bit>>5]&~(1<<(bit&0x1f)))|(value<<(bit&0x1f)); }
inline void bitClear(unsigned int *v, int bit) { v[bit>>5]&=~(1<<(bit&0x1f)); }
inline int bitTest(const unsigned int *v, int bit) { return (v[bit>>5]>>(bit&0x1f))&1; }

namespace MSTL
{

struct Magic
{
	unsigned int m_magic;
	Magic() :m_magic(0xabbad0d0) {}
	void test() { _ASSERT(m_magic==0xabbad0d0); }
	~Magic() { test(); m_magic = 0xde4db105; }
};

struct LinkedListElem
{
#if defined(UNITALLOCATOR_POINTERVALIDITY_TEST) || defined(UNITALLOCATOR_CHAIN_CHECK)
	Magic m_magic;
	inline void integrityCheck() {
		_ASSERT((unsigned int)this > 8);
		m_magic.test();
	}
#endif
	LinkedListElem *m_prev,*m_next;
	static inline void link(LinkedListElem *prev,LinkedListElem *next) { prev->m_next=next; next->m_prev=prev; } 
	template<typename T> static inline T *insert(T *elem,LinkedListElem *at) {
		elem->m_prev = at->m_prev;
		elem->m_next = at;
		at->m_prev->m_next = elem;
		at->m_prev         = elem;
		return elem;
	}
};

template<int ElemSize, int BlockSizeExp> struct MemoryUnits: public LinkedListElem
{
public:
	static const int BlockSize = 1 << BlockSizeExp;
	static const int ElemCount = (BlockSize+ElemSize-1) / ElemSize;
	char m_elems[ElemCount][ElemSize]; // must be first data member
	unsigned int m_allocBits[(ElemCount+31)/32];
	int m_firstFreeElem;
	int m_freeCount;
	inline static MemoryUnits *fromElemPtr(const void *elem) { 
		MemoryUnits *r = (MemoryUnits *)((int)elem-sizeof(LinkedListElem) & -BlockSize);
#ifdef UNITALLOCATOR_POINTERVALIDITY_TEST
		r->integrityCheck();
#endif
		return r; 
	}
	inline int getIndexFromElemPtr(const void *ptr) { return ((int)ptr-(int)m_elems)/ElemSize; }
	MemoryUnits(): m_firstFreeElem(0), m_freeCount(ElemCount)
	{
		memset(m_allocBits,0,sizeof(m_allocBits));
	}
	inline bool isEmpty() { return m_freeCount==ElemCount; }
	inline bool isFull() { return m_freeCount==0; }
	int allocIndex() {
		_ASSERT(m_freeCount);
		_ASSERT_VERBOSE(!bitTest(m_allocBits, m_firstFreeElem),_TVAR3(p,this,i,m_firstFreeElem,i,m_freeCount););
		bitSet(m_allocBits, m_firstFreeElem);
		m_freeCount--;
		int r = m_firstFreeElem;
		if (m_freeCount) {
			do {
				m_firstFreeElem++;
				_ASSERT(m_firstFreeElem<ElemCount);
			} while (bitTest(m_allocBits, m_firstFreeElem));
		} else
			m_firstFreeElem = ElemCount;
		return r;
	}
	void *alloc() {
		return m_elems[allocIndex()];
	}
	bool free(int i) {
		_ASSERT(m_freeCount<ElemCount);
		_ASSERT(bitTest(m_allocBits, i));
#ifdef MALLOC_WIPE
		memset(m_elems[i],0,sizeof(m_elems[i]));
#endif
		bitClear(m_allocBits, i);
		if (i<m_firstFreeElem)
			m_firstFreeElem = i;
		m_freeCount++;
		return isEmpty();
	}	
	inline bool free(void *elem) {
		return free(getIndexFromElemPtr(elem));
	}
};

template<typename ElemType_t, int ElemSize, int BlockSizeExp> class MemoryUnitsGC: public MemoryUnits<ElemSize, BlockSizeExp>
{
public:
	typedef ElemType_t ElemType;
	typedef MemoryUnits<ElemSize, BlockSizeExp> Super;
	unsigned int m_paintBits[(Super::ElemCount+31)/32];
	unsigned int m_paintBitPermanents[(Super::ElemCount+31)/32];
	inline static MemoryUnitsGC *fromElemPtr(const void *elem) { return (MemoryUnitsGC *)Super::fromElemPtr(elem); }
	inline void *alloc(void) {
		int i = Super::allocIndex();
		bitClear(this->m_paintBits,i);
		bitClear(this->m_paintBitPermanents,i);
#ifdef MALLOC_WIPE
		memset(this->m_elems[i],0,sizeof(this->m_elems[i]));
#endif
		return this->m_elems[i];
	}
	inline static bool paintPermanent(const void *p, int value)
	{
		MemoryUnitsGC *self=fromElemPtr(p);
		int i=self->getIndexFromElemPtr(p);
		bitSet(self->m_paintBits, i, value);
		bitSet(self->m_paintBitPermanents, i, value);
	}
	inline static bool paint(const void *p)
	{
		MemoryUnitsGC *self=fromElemPtr(p);
		int i=self->getIndexFromElemPtr(p);
		if (!bitTest(self->m_paintBits,i)) {
			bitSet(self->m_paintBits, i);
			return true;
		}
		return false;
	}
	int removeGarbage()
	{
		int i,counter = Super::ElemCount-this->m_freeCount;
		for(i=0;counter;i++) {
			if (bitTest(this->m_allocBits, i)) {
				if (!bitTest(this->m_paintBits, i)) 
				{
					((ElemType *)(this->m_elems[i]))->~ElemType();
					this->free(i);
				}
				else if (!bitTest(this->m_paintBitPermanents, i))
					bitClear(this->m_paintBits,i);
				counter--;
			}
		}
		return Super::ElemCount-this->m_freeCount;  // this is different value than in beginning
	}
};
 
#ifdef UNITALLOCATOR_ASSURESINGLETHREAD_TEST
extern int MEM_SEMA;
#define SEMA_ENTER _ASSERT(++MEM_SEMA==1)
#define SEMA_LEAVE _ASSERT(--MEM_SEMA==0)
#else
#define SEMA_ENTER
#define SEMA_LEAVE
#endif

template<typename Block > class MemoryUnitsAllocatorGeneric
{ 
protected:
	static void *allocBlock() {
		void *alloced= _aligned_malloc(sizeof(Block),Block::BlockSize);
#ifdef MALLOC_WIPE
		memset(alloced,0,sizeof(Block));
#endif
		return alloced;
	}
	static Block *createBlock() {
		return new (allocBlock()) Block();
	}
	static void freeBlock(Block *freed) {
#ifdef MALLOC_WIPE
		//todo: check that elements are still zero
		memset(freed,0,sizeof(Block));
#endif
		_aligned_free(freed);
	}
public:
	typedef Block BlockType;
	void *alloc();
	void free(void *p);
	//enum { blockElemCount = 0x10000/sizeof(Elem), blockEntryCount = 0x10000, c_blockSize=blockElemCount*sizeof(Elem) };
	MemoryUnitsAllocatorGeneric():m_first(this->createBlock()),m_emptyBlockCount(1) { Block::link(m_first,m_first); } 
protected:
	Block *m_first; // first part of list is always with non-full blocks 
	int m_emptyBlockCount;
	void integrityCheck();
}; 
template<typename Block> void MemoryUnitsAllocatorGeneric<Block>::integrityCheck()
{ 
	Block *b=m_first;
	IF_SHOW_UNITALLOCATOR_CHAIN(_ECHO("chain {"); _TVAR(i,Block::BlockSize);)
	_ASSERT(!b->isFull());
	for(;;) {
		if (b==0 || b->m_next->m_prev!=b || b->m_prev->m_next!=b) _ASSERT(0);
		b->integrityCheck();
		IF_SHOW_UNITALLOCATOR_CHAIN(_TVAR2(p,b,i,b->m_freeCount);)
		b=(Block *)b->m_next;
		if (b==m_first) break;
	}
	IF_SHOW_UNITALLOCATOR_CHAIN(_ECHO("chain }");)
}

template<typename Block> void *MemoryUnitsAllocatorGeneric<Block>::alloc()
{ 
	SEMA_ENTER;
	IF_UNITALLOCATOR_CHAIN_CHECK(integrityCheck();)
#ifdef MALLOC_COUNT
	mcounts.block++;
#endif
	if (m_first->isEmpty()) m_emptyBlockCount--;
	void *p=m_first->alloc();
	if (m_first->isFull()) {
		m_first = (BlockType *)(m_first->m_next);
		if (m_first->isFull()) { 
			m_first = BlockType::insert(this->createBlock(),m_first);
			m_emptyBlockCount++;
		}
	}
	IF_UNITALLOCATOR_CHAIN_CHECK(integrityCheck();)
	SEMA_LEAVE;
	return p;
}  

template<typename Block> void MemoryUnitsAllocatorGeneric<Block>::free(void *p)
{ 
	SEMA_ENTER;
	IF_UNITALLOCATOR_CHAIN_CHECK(integrityCheck();)
#ifdef MALLOC_COUNT
	mcounts.block--;
#endif
	BlockType *b=BlockType::fromElemPtr(p);
	if (b->isFull() && b!=m_first) {
		BlockType::link(b->m_prev, b->m_next);
		m_first = BlockType::insert(b, m_first);
		b->free((void *)p);
	}
	else if (b->free((void *)p)) {
		if (m_emptyBlockCount>0)
		{ if (m_first == b) m_first = (BlockType *)(b->m_next); 
			BlockType::link(b->m_prev, b->m_next);
			freeBlock(b); 
		}
		else m_emptyBlockCount++;
	} 
	IF_UNITALLOCATOR_CHAIN_CHECK(integrityCheck();)
	SEMA_LEAVE;
}

template<int ElemSize, int BlockSizeExp> class MemoryUnitsAllocator: public MemoryUnitsAllocatorGeneric<MemoryUnits<ElemSize,BlockSizeExp> > 
{ 
};

template<typename ElemType, int ElemSize, int BlockSizeExp> class MemoryUnitsAllocatorGC: public MemoryUnitsAllocatorGeneric< MemoryUnitsGC<ElemType,ElemSize,BlockSizeExp> > 
{ 
public:
	typedef MemoryUnitsAllocatorGeneric<MemoryUnitsGC<ElemType,ElemSize,BlockSizeExp> > Super;
	typedef typename Super::BlockType BlockType;
	inline bool paint(const void *p) { SEMA_ENTER; bool r=BlockType::paint(p); SEMA_LEAVE; return r;}
	inline void paintPermanent(const void *p,int value) { SEMA_ENTER; m_count+=1-value*2; BlockType::paintPermanent(p,value); SEMA_LEAVE; }
	int m_count;
	int m_lastUnitCount;
	void removeGarbage();
	void checkGarbage() {
#ifdef UNITALLOCATOR_PAINTCOMPLETENESS_TEST	
		if (m_count > 1)
#else
		if (m_count > m_lastUnitCount/4 + 10000)
#endif
			removeGarbage();
	}
	void *alloc() {
		m_count++;
		return Super::alloc();
	}
	MemoryUnitsAllocatorGC(): m_count(0),m_lastUnitCount(0) {}
};

template<typename ElemType, int ElemSize, int BlockSizeExp> void MemoryUnitsAllocatorGC<ElemType, ElemSize, BlockSizeExp>::removeGarbage()
{
	m_lastUnitCount=0;
	m_count=0;
	ElemType::GCStartPaint();
	SEMA_ENTER;
	IF_UNITALLOCATOR_CHAIN_CHECK(this->integrityCheck();)
	BlockType *b=this->m_first;
	for(;;) {
		BlockType *next=(BlockType *)(b->m_next);
		bool isLast = next == this->m_first; 
		bool isFull = b->isFull();
		SEMA_LEAVE;
		int left = b->removeGarbage();
		SEMA_ENTER;
		m_lastUnitCount+=left;
		{
			if (isFull && !b->isFull()) { 
				_ASSERT(b!=this->m_first);
				BlockType::link(b->m_prev, b->m_next);
				this->m_first = BlockType::insert(b, this->m_first);
				if (left==0)
					this->m_emptyBlockCount++;
			}
			else if (left==0) { 
				if (this->m_emptyBlockCount>0) { 
					BlockType::link(b->m_prev, b->m_next);
					this->freeBlock(b); 
					if (this->m_first == b)
						this->m_first = next; 
				}
				else this->m_emptyBlockCount++;
			} 

		}
		b=next;
		if (isLast) break;
	}	
	IF_UNITALLOCATOR_CHAIN_CHECK(this->integrityCheck();)
	SEMA_LEAVE;
}

}

#endif /* __MSTL_ALLOC_H__ */

